package 查找算法;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};
        int[] arr2 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
        int index = search3(arr2,0,arr2.length-1,1);
        if(index == -1){
            System.out.println("找不到");
        }else{
            System.out.println("找到了,索引为"+index);
        }

    }
    public static int search1(int[] arr,int value){
        int l = 0;
        int r = arr.length-1;
        while(l <= r){
            int mid = (l+r)>>>1;
            if(arr[mid] < value){
                l = mid+1;
            }else if(arr[mid] > value){
                    r = mid -1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    public static int search2(int[] arr,int value){
        int l = 0;
        int r = arr.length;// r 不作为查找的元素
        while(l < r){
            int mid = (l+r)>>>1;
            if(arr[mid] < value){
                l = mid+1;
            }else if(arr[mid] > value){
                r = mid;
            }
            else{
                return mid;
            }
        }
        return -1;
    }

    /**
     * 递归法
     * @param arr 要查找的数组,必须是有序的
     * @param left 左边索引
     * @param right 右边索引
     * @param fidVal 要查找的值
     * @return 找到了返回下标,找不到返回-1
     */
    public static int search3(int[] arr,int left,int right,int fidVal){
        System.out.println("1");
        if(left > right){
            return -1;
        }
        int mid = (left+right)>>>1;
        int midVal = arr[mid];
        if(fidVal < midVal){// 向左递归
            return search3(arr,left,mid-1,fidVal);
        }else if(fidVal > midVal){// 向右递归
            return search3(arr,mid+1,right,fidVal);
        }else{
            return mid;
        }
    }
}
